perm filename TREE.SAI[REV,MUS] blob
sn#254454 filedate 1977-05-24 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00017 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 ENTRY
C00006 00003 ∂ Record definitions used by this collection of routines
C00008 00004 INTERNAL RECORD_CLASS REV_TREE(
C00011 00005 INTERNAL BOOLEAN PROCEDURE is_root(
C00012 00006 INTERNAL BOOLEAN PROCEDURE move_tree(
C00020 00007 INTERNAL PROCEDURE first_node(
C00021 00008 INTERNAL PROCEDURE input_node(
C00023 00009 RECORD_POINTER(REV_TREE) PROCEDURE new_node(
C00024 00010 INTERNAL PROCEDURE free_node(
C00026 00011 INTERNAL RECORD_POINTER(REV_TREE) PROCEDURE new_tree
C00027 00012 INTERNAL PROCEDURE insert_node(
C00034 00013 INTERNAL PROCEDURE delete_node(
C00037 00014 INTERNAL PROCEDURE free_tree(
C00038 00015 INTERNAL BOOLEAN PROCEDURE traverse_tree(
C00041 00016 INTERNAL RECORD_POINTER(CASCADE) PROCEDURE new_cascade(
C00049 00017 END "TREE"
C00050 ENDMK
C⊗;
ENTRY;
BEGIN "TREE"
REQUIRE "HEADER.SAI" SOURCE_FILE;
∂ Ken Shoemake. December 1976.
This module defines the concept of a tree of reverberators, where the root
is interpreted as a monophonic input signal and leaves are interpreted as
connected to output channels. All units in the tree are constrained to have
the same clock rate.
The major routines are MOVE_TREE, INSERT_NODE, DELETE_NODE, and TRAVERSE_TREE.
Also of interest are FIRST_NODE and IS_ROOT. The first class of routines
serve rather obvious functions, with the following additional specification:
a tree traversal is performed in PRE-ORDER fashion,
i.e., at any node, first that node, then its output, then its output's branches
are visited. The traversal is done in co-routine fashion, with successive
calls of TRAVERSE_TREE delivering successive nodes in the defined order.
The other two routines respectively move the tree to the root, and test whether
the tree position is at the root.
Tree moving requires some clarification: A tree is assumed to be an entity
dangling by one of its nodes, so that "moving the tree" means changing the
node by which it dangles (without actually altering the tree structure).
Trees can move in the following directions:
INPUT - Towards root away from leaves
OUTPUT - Away from root towards leaves
BRANCH - Parallel node with same INPUT as SELF
SELF - Don't go anywhere (Really is meaningful)
Insertions can also occur in the above directions.
;
∂ Record definitions used by this collection of routines;
EXTERNAL RECORD_CLASS REV_UNIT(
INTEGER NUMBER_OF_SAMPLES, CLOCK_RATE;
REAL GAIN, DELAY_TIME, DECAY_TIME);
EXTERNAL REAL PROCEDURE get_spec(
RECORD_POINTER(REV_UNIT) revrb;
STRING which_spec);
EXTERNAL PROCEDURE copy_unit(
REFERENCE RECORD_POINTER(REV_UNIT) new_copy;
RECORD_POINTER(REV_UNIT) unit);
EXTERNAL PROCEDURE free_unit(
REFERENCE RECORD_POINTER(REV_UNIT) unit);
EXTERNAL RECORD_CLASS REV_STATE_LIST(
RECORD_POINTER(REV_STATE_LIST) NEXT_UNIT;
REAL ARRAY DELAY_MEM; INTEGER MEM_SIZE, MEM_POSITION; REAL GAIN);
EXTERNAL RECORD_CLASS CASCADE(
INTEGER CLOCK_RATE;
RECORD_POINTER(REV_STATE_LIST) FIRST_UNIT);
EXTERNAL PROCEDURE add_unit(
REFERENCE RECORD_POINTER(CASCADE) chain;
RECORD_POINTER(REV_UNIT) unit);
INTERNAL RECORD_CLASS REV_TREE(
RECORD_POINTER(REV_TREE) IN, OUT, ABURO;
RECORD_POINTER(REV_UNIT) UNIT);
∂ I feel that an explanation is in order for the name "ABURO" used in
the definition above. It is a Yoruba (Nigerian) kinship term
meaning "younger sibling". Here it is used to enable us to
get to branch TREEs having the same input. All of the tree
manipulating routines preserve the property that
IN[ABURO[node]] = IN[node],
as well as a few others. All units in a tree will have the
same CLOCK_RATE, and only the unique ROOT node of a tree will
have a null UNIT. The ROOT will have null IN and ABURO links.
In other words, we intend for REV_TREEs to have the following
structure:
+--------+--------+--------+--------+
| | | | |
| ↑ in | ↓ out | → aburo| UNIT |
| | | | |
+--------+--------+--------+--------+
+-----+
| |
|root |
| |
+-----+
out |
\|/
+-----+
| |
| R11 |
=-->| |<--=
| +-----+ |
in | out | |
| \|/ | in
| +-----+ | +-----+
=---| | =-----| |
| R21 | | R22 |
=-->| |-------->| |--------> ≡null_record≡
| +-----+ aburo +-----+ aburo
in | out | out|
| \|/ \|/
| +-----+ .
=---| | .
| R31 | .
| |---->...
+-----+ aburo
out |
\|/
≡null_record≡
;
INTERNAL BOOLEAN PROCEDURE is_root(
RECORD_POINTER(REV_TREE) node);
∂ Returns TRUE is tree is at its root.
;
RETURN(REV_TREE:IN[node] = NULL_RECORD);
INTERNAL BOOLEAN PROCEDURE move_tree(
REFERENCE RECORD_POINTER(REV_TREE) node;
REFERENCE RECORD_POINTER(REV_UNIT) unit;
STRING direction("OUTPUT"));
∂ Moves the tree in the indicated direction, copying the unit found
at the resulting node into the appropriate argument. Returns TRUE
if the requested move was possible, FALSE otherwise. (SELF is useful
here for getting a copy of the unit at the current node.)
;
BEGIN "move tree"
DEFINE move(dir)=⊂
IF
REV_TREE:dir[node] = NULL_RECORD
THEN
RETURN(FALSE)
ELSE BEGIN
copy_unit(unit,REV_TREE:UNIT[node ← REV_TREE:dir[node]]);
RETURN(TRUE);
END⊃;
DEFINE error(range)=⊂PRINT(↓,"move_tree: ",range,↓)⊃;
IF
node = NULL_RECORD
THEN
RETURN(FALSE);
IF
EQU(direction,"SELF")
THEN BEGIN
copy_unit(unit,REV_TREE:UNIT[node]);
RETURN(TRUE);
END
ELSE IF
EQU(direction,"INPUT")
THEN
move(IN)
ELSE IF
EQU(direction,"OUTPUT")
THEN
move(OUT)
ELSE IF
EQU(direction,"BRANCH")
THEN
move(ABURO)
ELSE
error("direction ε {BRANCH,INPUT,OUTPUT,SELF}");
END "move tree";
INTERNAL PROCEDURE first_node(
REFERENCE RECORD_POINTER(REV_TREE) node);
∂ Moves the tree to its root.
;
BEGIN "first node"
RECORD_POINTER(REV_UNIT) unit;
WHILE
move_tree(node,unit,"INPUT")
DO;
END "first node";
INTERNAL PROCEDURE input_node(
REFERENCE RECORD_POINTER(REV_TREE) node);
∂ Moves the tree to the unique node that actually points at the
given node. The pointing can be either by an OUT pointer or an
ABURO pointer. This is primarily a utility for other programs
in this module.
;
BEGIN "input node"
RECORD_POINTER(REV_TREE) knows;
knows ← NULL_RECORD;
IF
REV_TREE:IN[node] ≠ NULL_RECORD
THEN BEGIN
knows ← REV_TREE:IN[node];
IF
knows ≠ NULL_RECORD
THEN
IF
REV_TREE:OUT[knows] ≠ node
THEN BEGIN
knows ← REV_TREE:OUT[knows];
WHILE
REV_TREE:ABURO[knows] ≠ node
DO
knows ← REV_TREE:ABURO[knows];
END;
END;
node ← knows;
END "input node";
RECORD_POINTER(REV_TREE) PROCEDURE new_node(
RECORD_POINTER(REV_UNIT) unit);
∂ Allocates a new node containing the argument unit.
;
BEGIN "new node"
RECORD_POINTER(REV_TREE) node;
node ← NEW_RECORD(REV_TREE);
copy_unit(REV_TREE:UNIT[node],unit);
REV_TREE:IN[node] ←
REV_TREE:OUT[node] ←
REV_TREE:ABURO[node] ← NULL_RECORD;
RETURN(node);
END "new node";
INTERNAL PROCEDURE free_node(
REFERENCE RECORD_POINTER(REV_TREE) node);
∂ Deallocates the space for the given node, including the unit contained
in it. Be sure the are no references to the node left dangling by its
demise. Sets the pointer to NULL_RECORD.
;
BEGIN "free node"
∂ BEWARE ... Nobody else but argument better point at record.;
∂ PROCEDURE TO CALL A RECORD'S HANDLER PROCEDURE;
EXTERNAL RECORD_POINTER(ANY_CLASS) PROCEDURE $RECFN(
INTEGER OP;
RECORD_POINTER(ANY_CLASS) R);
∂ OP VALUES FOR $RECFN;
DEFINE ALLOCATE_RECORD = 1;
DEFINE MARK_SUBFIELDS = 4;
DEFINE DELETE_RECORD = 5;
IF
node = NULL_RECORD
THEN
RETURN;
REV_TREE:IN[node] ←
REV_TREE:OUT[node] ←
REV_TREE:ABURO[node] ← NULL_RECORD;
free_unit(REV_TREE:UNIT[node]);
$RECFN(DELETE_RECORD,node);
node ← NULL_RECORD;
END "free node";
INTERNAL RECORD_POINTER(REV_TREE) PROCEDURE new_tree;
∂ Creates a new tree with only a root node.
;
RETURN(new_node(NULL_RECORD));
INTERNAL PROCEDURE insert_node(
REFERENCE RECORD_POINTER(REV_TREE) node;
RECORD_POINTER(REV_UNIT) unit;
STRING direction("OUTPUT");
BOOLEAN replace(FALSE));
∂ Insert a new node in the given tree in the given direction. If replace
is TRUE then just overwrite the parameters of the node in that direction.
(This is one reason for SELF moves.) If not replacing, then a copy of
the given unit is made if it is compatible with the tree. This routine
keeps all the links properly updated, a slightly hairy undertaking.
;
BEGIN "insert node"
RECORD_POINTER(REV_TREE) inserted, knows;
RECORD_POINTER(REV_UNIT) tmp_unit;
DEFINE error(range)=⊂PRINT(↓,"insert_node: ",range,↓)⊃;
IF
unit = NULL_RECORD
THEN BEGIN
error("unit ≠ null_record");
RETURN;
END;
IF
node = NULL_RECORD
THEN BEGIN
error("node ≠ null_record");
RETURN;
END;
IF
is_root(node)
THEN BEGIN
IF
move_tree(node,tmp_unit,"OUTPUT")
THEN BEGIN
IF
get_spec(unit,"rate") ≠ get_spec(tmp_unit,"rate")
THEN BEGIN
error("Rates must be consistent");
move_tree(node,tmp_unit,"INPUT");
RETURN;
END
ELSE
move_tree(node,tmp_unit,"INPUT");
END
END
ELSE
IF
get_spec(unit,"rate") ≠ get_spec(REV_TREE:UNIT[node],"rate")
THEN BEGIN
error("Rates must be consistent");
RETURN;
END;
IF
replace ∧ move_tree(node,tmp_unit,direction)
THEN BEGIN
IF
is_root(node)
THEN
error("Can't replace root")
ELSE
copy_unit(REV_TREE:UNIT[node],unit);
RETURN;
END;
IF
EQU(direction,"SELF")
THEN BEGIN
error("SELF can only be replaced");
RETURN;
END
ELSE IF
EQU(direction,"BRANCH")
THEN BEGIN
IF
is_root(node)
THEN BEGIN
error("node ≠ root");
RETURN;
END;
inserted ← new_node(unit);
REV_TREE:ABURO[inserted] ← REV_TREE:ABURO[node];
REV_TREE:ABURO[node] ← inserted;
REV_TREE:IN[inserted] ← REV_TREE:IN[node];
node ← inserted;
RETURN;
END
ELSE IF
EQU(direction,"INPUT")
THEN BEGIN
IF
is_root(node)
THEN BEGIN
error("node ≠ root");
RETURN;
END;
inserted ← new_node(unit);
REV_TREE:ABURO[inserted] ← REV_TREE:ABURO[node];
REV_TREE:ABURO[node] ← NULL_RECORD;
REV_TREE:IN[inserted] ← REV_TREE:IN[node];
REV_TREE:IN[node] ← inserted;
REV_TREE:OUT[inserted] ← node;
knows ← REV_TREE:IN[inserted];
IF
knows ≠ NULL_RECORD
THEN
IF
REV_TREE:OUT[knows] ≠ node
THEN BEGIN
knows ← REV_TREE:OUT[knows];
WHILE
REV_TREE:ABURO[knows] ≠ node
DO
knows ← REV_TREE:ABURO[knows];
REV_TREE:ABURO[knows] ← inserted;
END
ELSE
REV_TREE:OUT[knows] ← inserted;
node ← inserted;
RETURN;
END
ELSE IF
EQU(direction,"OUTPUT")
THEN BEGIN
inserted ← new_node(unit);
REV_TREE:IN[inserted] ← node;
REV_TREE:OUT[inserted] ← REV_TREE:OUT[node];
REV_TREE:OUT[node] ← inserted;
node ← REV_TREE:OUT[inserted];
WHILE
node ≠ NULL_RECORD
DO BEGIN
REV_TREE:IN[node] ← inserted;
node ← REV_TREE:ABURO[node];
END;
node ← inserted;
RETURN;
END
ELSE BEGIN
error("direction ε {BRANCH,INPUT,OUTPUT,SELF}");
RETURN;
END;
END "insert node";
INTERNAL PROCEDURE delete_node(
REFERENCE RECORD_POINTER(REV_TREE) node);
BEGIN "delete node"
∂ Remove the node the tree is at from the tree. Reclaim all associated
storage, and move the tree to either the replacement node moving up --
if one exists -- or to the INPUT of the deleted node.
;
RECORD_POINTER(REV_TREE) knows, replacement;
DEFINE error(range)=⊂PRINT(↓,"delete_node: ",range,↓)⊃;
IF
is_root(node)
THEN BEGIN
error("node ≠ root");
RETURN;
END;
IF
node = NULL_RECORD
THEN
RETURN;
IF
REV_TREE:OUT[node] = NULL_RECORD
THEN
replacement ← REV_TREE:ABURO[node]
ELSE BEGIN
replacement ← REV_TREE:OUT[node];
REV_TREE:IN[replacement] ← REV_TREE:IN[node];
WHILE
REV_TREE:ABURO[replacement] ≠ NULL_RECORD
DO BEGIN
replacement ← REV_TREE:ABURO[replacement];
REV_TREE:IN[replacement] ← REV_TREE:IN[node];
END;
REV_TREE:ABURO[replacement] ← REV_TREE:ABURO[node];
replacement ← REV_TREE:OUT[node];
END;
IF
REV_TREE:IN[node] ≠ NULL_RECORD
THEN BEGIN
knows ← REV_TREE:IN[node];
IF
knows ≠ NULL_RECORD
THEN
IF
REV_TREE:OUT[knows] ≠ node
THEN BEGIN
knows ← REV_TREE:OUT[knows];
WHILE
REV_TREE:ABURO[knows] ≠ node
DO
knows ← REV_TREE:ABURO[knows];
REV_TREE:ABURO[knows] ← replacement;
END
ELSE
REV_TREE:OUT[knows] ← replacement;
END;
knows ← node;
IF
replacement = NULL_RECORD
THEN
node ← REV_TREE:IN[node]
ELSE
node ← replacement;
free_node(knows);
END "delete node";
INTERNAL PROCEDURE free_tree(
REFERENCE RECORD_POINTER(REV_TREE) node);
∂ Free all the storage associated with the tree. Returns the
NULL_RECORD in the pointer.
;
BEGIN "free tree"
RECORD_POINTER(REV_UNIT) unit;
first_node(node);
move_tree(node,unit,"OUTPUT");
WHILE
node ≠ NULL_RECORD ∧ ¬is_root(node)
DO
delete_node(node);
END "free tree";
INTERNAL BOOLEAN PROCEDURE traverse_tree(
REFERENCE RECORD_POINTER(REV_TREE) node;
REFERENCE RECORD_POINTER(REV_UNIT) unit;
REFERENCE INTEGER level;
REFERENCE BOOLEAN branching);
∂ Do a pre-order tree walk in coroutine fashion. Each call moves the
tree to the next node in the traversal order and delivers the unit
found there. A pre-order traversal at any node is that node, traverse
its first OUTPUT, then traverse the rest of its OUTPUTs in succession.
Level is modified with the change in level as the traversal proceeds.
Branching accumulates whether there has been any branching so far.
;
BEGIN "traverse tree"
IF
node = NULL_RECORD
THEN
RETURN(FALSE);
branching ← branching ∨ REV_TREE:ABURO[node] ≠ NULL_RECORD;
IF
move_tree(node,unit,"OUTPUT")
THEN BEGIN
level ← level+1;
branching ← branching ∨ REV_TREE:ABURO[node] ≠ NULL_RECORD;
RETURN(TRUE);
END;
WHILE
¬move_tree(node,unit,"BRANCH")
DO
IF
move_tree(node,unit,"INPUT")
THEN
level ← level-1
ELSE
RETURN(FALSE);
branching ← TRUE;
RETURN(TRUE);
END "traverse tree";
INTERNAL RECORD_POINTER(CASCADE) PROCEDURE new_cascade(
RECORD_POINTER(REV_TREE) node;
INTEGER path_length(INFINITY));
∂ This routine is for constructing a cascade from the current
location towards the root, optionally restricted to the given length.
The cascade can then be passed to IMPULS to obtain an impulse response
for that path.
;
BEGIN "new cascade"
RECORD_POINTER(CASCADE) chain;
RECORD_POINTER(REV_UNIT) unit;
chain ← NULL_RECORD;
IF
¬move_tree(node,unit,"SELF")
∨
is_root(node)
∨
path_length ≤ 0
THEN
RETURN(chain);
add_unit(chain,unit);
WHILE
move_tree(node,unit,"INPUT")
∧
¬is_root(node)
∧
(path_length ← path_length-1) > 0
DO
add_unit(chain,unit);
RETURN(chain);
END "new cascade";
END "TREE"